package com.sjc.algorithm.sort;

import java.util.Arrays;

/**
 * 冒泡排序
 * @author by SangJiacun
 * @Date 2020/5/11 17:30
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] array = new int[]{4,7,1,43,76,98,23,22,88,102};
        System.out.println(Arrays.toString(array));

//        BubbleSortV1(array);
//        BubbleSortV2(array);
        cocktailSort(array);
        System.out.println(Arrays.toString(array));

    }

    /**
     * 版本1.0
     * @param array
     */
    public static void BubbleSortV1(int[] array){
        int times = 0;
        for(int i=0; i<array.length; i++){
            for(int j=0; j<array.length-i-1; j++){
                if(array[j] < array[j+1]){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
            times++;
        }
        System.out.println("times -->" + times);
    }

    /**
     * 有序边界，但没啥用啊？
     * @param array
     */
    public static void BubbleSortV2(int[] array){
        int times = 0;
        //最后一次交换的位置
        int lastExchangeIndex = 0;
        int sortBorder = array.length - 1;

        for(int i=0; i<array.length; i++){
            //有序标记，每一轮的初始值都是true
            boolean isSorted = true;

            for(int j=0; j<array.length-i-1; j++){
                if(array[j] < array[j+1]){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;

                    isSorted = false;
                    lastExchangeIndex = j;
                }
            }
            times++;
            sortBorder = lastExchangeIndex;
            if(isSorted){
                break;
            }
        }
        System.out.println("times -->" + times);
    }

    /**
     * 鸡尾酒排序  钟摆
     * @param array
     */
    public static void cocktailSort(int[] array){
        int times=0;
        for(int i=0; i<array.length/2; i++){
            for(int j=i;j<array.length-i-1;j++){
                if(array[j] > array[j+1]){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
            for(int j = array.length-i-1;j>i; j--){
                if(array[j] < array[j-1]){
                    int temp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = temp;
                }
            }
            times++;
        }
        System.out.println("times -->" + times);
    }
}
